home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / pluginy Firefox / 1865 / 1865.xpi / chrome / adblockplus.jar / content / matcher.js < prev    next >
Text File  |  2010-01-07  |  6KB  |  255 lines
  1. /* ***** BEGIN LICENSE BLOCK *****
  2.  * Version: MPL 1.1
  3.  *
  4.  * The contents of this file are subject to the Mozilla Public License Version
  5.  * 1.1 (the "License"); you may not use this file except in compliance with
  6.  * the License. You may obtain a copy of the License at
  7.  * http://www.mozilla.org/MPL/
  8.  *
  9.  * Software distributed under the License is distributed on an "AS IS" basis,
  10.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  11.  * for the specific language governing rights and limitations under the
  12.  * License.
  13.  *
  14.  * The Original Code is Adblock Plus.
  15.  *
  16.  * The Initial Developer of the Original Code is
  17.  * Wladimir Palant.
  18.  * Portions created by the Initial Developer are Copyright (C) 2006-2009
  19.  * the Initial Developer. All Rights Reserved.
  20.  *
  21.  * Contributor(s):
  22.  *
  23.  * ***** END LICENSE BLOCK ***** */
  24.  
  25. /**
  26.  * @fileOverview Matcher class implementing matching addresses against a list of filters.
  27.  * This file is included from AdblockPlus.js.
  28.  */
  29.  
  30. /**
  31.  * Blacklist/whitelist filter matching
  32.  * @constructor
  33.  */
  34. function Matcher()
  35. {
  36.     this.clear();
  37. }
  38.  
  39. /**
  40.  * Length of a filter shortcut
  41.  * @type Number
  42.  */
  43. Matcher.shortcutLength = 8;
  44.  
  45. /**
  46.  * Maximal number of matching cache entries to be kept
  47.  * @type Number
  48.  */
  49. Matcher.maxCacheEntries = 1000;
  50.  
  51. Matcher.prototype = {
  52.     /**
  53.      * Lookup table for filters by their shortcut
  54.      * @type Object
  55.      */
  56.     shortcutHash: null,
  57.  
  58.     /**
  59.      * Should be true if shortcutHash has any entries
  60.      * @type Boolean
  61.      */
  62.     hasShortcuts: false,
  63.  
  64.     /**
  65.      * Filters without a shortcut
  66.      * @type Array of RegExpFilter
  67.      */
  68.     regexps: null,
  69.  
  70.     /**
  71.      * Lookup table, has keys for all filters already added
  72.      * @type Object
  73.      */
  74.     knownFilters: null,
  75.  
  76.     /**
  77.      * Lookup table of previous matchesAny results
  78.      * @type Object
  79.      */
  80.     resultCache: null,
  81.  
  82.     /**
  83.      * Number of entries in resultCache
  84.      * @type Number
  85.      */
  86.     cacheEntries: 0,
  87.  
  88.     /**
  89.      * Removes all known filters
  90.      */
  91.     clear: function()
  92.     {
  93.         this.shortcutHash = {__proto__: null};
  94.         this.hasShortcuts = false;
  95.         this.regexps = [];
  96.         this.knownFilters = {__proto__: null};
  97.         this.resultCache = {__proto__: null};
  98.         this.cacheEntries = 0;
  99.     },
  100.  
  101.     /**
  102.      * Adds a filter to the matcher
  103.      * @param {RegExpFilter} filter
  104.      */
  105.     add: function(filter)
  106.     {
  107.         if (filter.text in this.knownFilters)
  108.             return;
  109.  
  110.         // Look for a suitable shortcut if the current can't be used
  111.         if (!filter.shortcut || filter.shortcut in this.shortcutHash)
  112.             filter.shortcut = this.findShortcut(filter.text);
  113.  
  114.         if (filter.shortcut) {
  115.             this.shortcutHash[filter.shortcut] = filter;
  116.             this.hasShortcuts = true;
  117.         }
  118.         else 
  119.             this.regexps.push(filter);
  120.  
  121.         this.knownFilters[filter.text] = true;
  122.         if (this.cacheEntries > 0)
  123.         {
  124.             this.resultCache = {__proto__: null};
  125.             this.cacheEntries = 0;
  126.         }
  127.     },
  128.  
  129.     /**
  130.      * Removes a filter from the matcher
  131.      * @param {RegExpFilter} filter
  132.      */
  133.     remove: function(filter)
  134.     {
  135.         if (!(filter.text in this.knownFilters))
  136.             return;
  137.  
  138.         if (filter.shortcut)
  139.             delete this.shortcutHash[filter.shortcut];
  140.         else
  141.         {
  142.             let i = this.regexps.indexOf(filter);
  143.             if (i >= 0)
  144.                 this.regexps.splice(i, 1);
  145.         }
  146.  
  147.         delete this.knownFilters[filter.text];
  148.         if (this.cacheEntries > 0)
  149.         {
  150.             this.resultCache = {__proto__: null};
  151.             this.cacheEntries = 0;
  152.         }
  153.     },
  154.  
  155.     /**
  156.      * Looks up a free shortcut for a filter
  157.      * @param {String} text text representation of the filter
  158.      * @return {String} shortcut or null
  159.      */
  160.     findShortcut: function(text)
  161.     {
  162.         if (Filter.regexpRegExp.test(text))
  163.             return null;
  164.  
  165.         text = text.replace(Filter.optionsRegExp, "").replace(/^@@/, "")
  166.                              .replace(/^\|{1,2}/, "").replace(/\|$/, "")
  167.                              .replace(/\^/g, "*").toLowerCase();
  168.  
  169.         let len = Matcher.shortcutLength;
  170.         let numCandidates = text.length - len + 1;
  171.         let startingPoint = Math.floor((text.length - len) / 2);
  172.         for (let i = 0, j = 0; i < numCandidates; i++, (j > 0 ? j = -j : j = -j + 1))
  173.         {
  174.             let candidate = text.substr(startingPoint + j, len);
  175.             if (candidate.indexOf("*") < 0 && !(candidate in this.shortcutHash))
  176.                 return candidate;
  177.         }
  178.         return null;
  179.     },
  180.  
  181.     /**
  182.      * Same as matchesAny but bypasses result cache
  183.      */
  184.     matchesAnyInternal: function(location, contentType, docDomain, thirdParty)
  185.     {
  186.         if (this.hasShortcuts)
  187.         {
  188.             // Optimized matching using shortcuts
  189.             let text = location.toLowerCase();
  190.             let len = Matcher.shortcutLength;
  191.             let endPos = text.length - len + 1;
  192.             for (let i = 0; i <= endPos; i++)
  193.             {
  194.                 let substr = text.substr(i, len);
  195.                 if (substr in this.shortcutHash)
  196.                 {
  197.                     let filter = this.shortcutHash[substr];
  198.                     if (filter.matches(location, contentType, docDomain, thirdParty))
  199.                         return filter;
  200.                 }
  201.             }
  202.         }
  203.  
  204.         // Slow matching for filters without shortcut
  205.         for each (let filter in this.regexps)
  206.             if (filter.matches(location, contentType, docDomain, thirdParty))
  207.                 return filter;
  208.  
  209.         return null;
  210.     },
  211.  
  212.     /**
  213.      * Tests whether the URL matches any of the known filters
  214.      * @param {String} location URL to be tested
  215.      * @param {String} contentType content type identifier of the URL
  216.      * @param {String} docDomain domain name of the document that loads the URL
  217.      * @param {Boolean} thirdParty should be true if the URL is a third-party request
  218.      * @return {RegExpFilter} matching filter or null
  219.      */
  220.     matchesAny: function(location, contentType, docDomain, thirdParty)
  221.     {
  222.         let key = location + " " + contentType + " " + docDomain + " " + thirdParty;
  223.         if (key in this.resultCache)
  224.             return this.resultCache[key];
  225.  
  226.         let result = this.matchesAnyInternal(location, contentType, docDomain, thirdParty);
  227.  
  228.         if (this.cacheEntries >= Matcher.maxCacheEntries)
  229.         {
  230.             this.resultCache = {__proto__: null};
  231.             this.cacheEntries = 0;
  232.         }
  233.     
  234.         this.resultCache[key] = result;
  235.         this.cacheEntries++;
  236.  
  237.         return result;
  238.     }
  239. };
  240. abp.Matcher = Matcher;
  241.  
  242. /**
  243.  * Matcher instance for blocking filters
  244.  * @type Matcher
  245.  */
  246. var blacklistMatcher = new Matcher();
  247. abp.blacklistMatcher = blacklistMatcher;
  248.  
  249. /**
  250.  * Matcher instance for exception rules
  251.  * @type Matcher
  252.  */
  253. var whitelistMatcher = new Matcher();
  254. abp.whitelistMatcher = whitelistMatcher;
  255.